package DataStructures.Search;

import java.util.ArrayList;
import java.util.List;

//使用二分查找的前提是 该数组是有序的
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1,8,10,89,1000,1000,1000,1000,1234};
        int resIndex = binarySearch(arr,0,arr.length - 1,1234);
        System.out.println(resIndex);

        //第二种查询方式
        List<Integer> resIndexList = binarySearch2(arr,0,arr.length - 1,1000);
        System.out.println(resIndexList);
    }

    //二分查找
    //arr 左边的索引
    //left 左边的索引
    //right 右边的索引
    //findVal 要查找的值
    //return 如果找到就返回下标 如果没找到 就返回-1
    public static int binarySearch(int[] arr,int left,int right,int findVal) {
        //当left > right时候 说明已经递归了整个数组 但是没有找到
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (findVal > midVal) {//向右递归
            return binarySearch(arr,mid + 1,right,findVal);
        }else if (findVal < midVal) {//向左
            return binarySearch(arr,left,mid - 1,findVal);
        }else {
            return mid;
        }
    }

    //完成一个课后思考题
    //当一个有序数组{1,8,10,89,1000,1000,1234} 有多个相同的数值时 如何将所有的数值都查找到 比如1000
    //思路分析:
    //在找到mid值时 不要马上返回
    //向mid索引值的左边扫描 将所有满足1000的下标加入到集合ArrayList
    //向mid索引值的右边扫描 将所有满足1000的下标加入到集合ArrayList
    //将ArrayList返回
    public static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
        //当left > right时候 说明已经递归了整个数组 但是没有找到
        if (left > right) {
            //return -1;
            //此时就不能返回-1了 我们可以返回一个空的ArrayList
            return new ArrayList<Integer>();
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (findVal > midVal) {//向右递归
            return binarySearch2(arr,mid + 1,right,findVal);
        }else if (findVal < midVal) {//向左
            return binarySearch2(arr,left,mid - 1,findVal);
        }else {
            //思路分析:
            //在找到mid值时 不要马上返回
            //向mid索引值的左边扫描 将所有满足1000的下标加入到集合ArrayList
            //向mid索引值的右边扫描 将所有满足1000的下标加入到集合ArrayList
            //将ArrayList返回
            ArrayList<Integer> resIndexList = new ArrayList<Integer>();
            //先处理左边的
            int temp = mid - 1;
            while (true) {
                if (temp < 0 || arr[temp] != findVal) {//退出
                    break;
                }
                //否则 就把temp放入到集合中
                resIndexList.add(temp);
                //指针左移
                temp--;
            }
            //再处理中间
            resIndexList.add(mid);
            //再处理右边的
            temp = mid + 1;
            while (true) {
                if (temp > arr.length - 1 || arr[temp] != findVal) {
                    break;
                }
                resIndexList.add(temp);
                temp++;
            }
            return resIndexList;
        }
    }
}
